package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 基于二叉查找树的有序符号表
 * put：O(lgN)
 * get：O(lgN)
 * 当面对最坏的输入情况时，效率很糟糕
 * 
 * @author 付大石
 */
public class BinarySearchTreeST<K extends Comparable<K>, V> {

    public static void main(String[] args) {

        BinarySearchTreeST<Character, Integer> st = new BinarySearchTreeST<Character, Integer>();
        st.put('S', 0);
        st.put('E', 1);
        st.put('A', 2);
        st.put('R', 3);
        st.put('C', 4);
        st.put('H', 5);
        st.put('E', 6);
        st.put('X', 7);
        st.put('A', 8);
        st.put('M', 9);
        st.put('P', 10);
        st.put('L', 11);
        st.put('E', 12);
        for (Character item : st.keys()) {
            System.out.println(item + "   " + st.get(item));
        }
    }

    private Node root;

    public BinarySearchTreeST() {

    }

    public void put(K key, V value) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (value == null) {
            delete(key);
			return ;
        }
        root = put(root, key, value);
    }

    public Node put(Node node, K key, V value) {

        if (node == null) {
            return new Node(key, value);
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) { // 插入左子树
            node.left = put(node.left, key, value);
        } else if (cmp < 0) { // 插入右子树
            node.right = put(node.right, key, value);
        } else {
            node.value = value;
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 获取{@code key}所对应的键值对的值
     * 
     * @param key
     * @return
     */
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node node, K key) {

        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) { // 在左子树中查找
            return get(node.left, key);
        } else if (cmp < 0) { // 在右子树中查找
            return get(node.right, key);
        } else {
            return node.value;
        }
    }

    public void delete(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (isEmpty()) {
            throw new RuntimeException("符号表为空");
        }
        root = delete(root, key);
    }

    public Node delete(Node node, K key) {

        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            node.left = delete(node.left, key);
        } else if (cmp < 0) {
            node.right = delete(node.right, key);
        } else {
            if (node.right != null && node.left != null) { // 左右子树均不为null

                Node temp = min(node.right);
                temp.right = deleteMin(node.right);
                temp.left = node.left;
                node = temp;
            } else if (node.right != null) { // 右子树不为null
                return node.right;
            } else if (node.left != null) { // 左子树不为null
                return node.left;
            }
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    public boolean contains(K key) {
        return get(key) != null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 获取符号表的大小
     * @return
     */
    public int size() {
        return size(root);
    }

    /**
     * 获取以node为根节点的树的大小
     * 
     * @param node
     * @return
     */
    private int size(Node node) {

        if (node == null) {
            return 0;
        }
        return node.size;
    }

    /**
     * 获取符号表中的最小值
     * 
     * @return
     */
    public K min() {

        if (isEmpty()) {
            throw new RuntimeException("符号表为空");
        }
        Node node = min(root);
        return node == null ? null : node.key;
    }

    private Node min(Node node) {

        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    /**
     * 获取符号表中的最大值
     * 
     * @return
     */
    public K max() {

        Node node = max(root);
        return node == null ? null : node.key;
    }

    private Node max(Node node) {

        if (node.right == null) {
            return node;
        }
        return max(node.right);
    }

    /**
     * 向下取整
     * 
     * @param key
     * @return
     */
    public K floor(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        Node node = floor(root, key);
        return node == null ? null : node.key;
    }

    private Node floor(Node node, K key) {

        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            return floor(node.left, key);
        } else if (cmp < 0) {
            Node temp = floor(node.right, key);
            return temp == null ? node : temp;
        } else {
            return node;
        }
    }

    /**
     * 向上取整
     * 
     * @param key
     * @return
     */
    public K ceiling(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        Node node = ceiling(root, key);
        return node == null ? null : node.key;
    }

    private Node ceiling(Node node, K key) {

        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            Node temp = ceiling(node.left, key);
            return temp == null ? node : temp;
        } else if (cmp < 0) {
            return ceiling(node.right, key);
        } else {
            return node;
        }
    }

    /**
     * 获取符号表中，{@code key}对应的键值对的排名
     * 
     * @param key
     * @return
     */
    public int rank(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        return rank(root, key);
    }

    public int rank(Node node, K key) {

        if (node == null) {
            return 0;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            return rank(node.left, key);
        } else if (cmp < 0) {
            return rank(node.right, key) + size(node.left) + 1;
        } else {
            return size(node.left);
        }
    }

    /**
     * 获取符号表中，第{@code k}个键值对的键
     * 
     * @param k
     * @return
     */
    public K select(int k) {

        Node node = select(root, k);
        return node == null ? null : node.key;
    }

    private Node select(Node node, int k) {

        if (node == null) {
            return null;
        }
        int t = size(node.left);
        System.out.println(node.key + "   " + t);
        if (t > k) {
            return select(node.left, k);
        } else if (t < k) {
            return select(node.right, k - t - 1);
        } else {
            return node;
        }
    }

    public void deleteMin() {

        if (isEmpty()) {
            throw new RuntimeException("符号表为空");
        }
        root = deleteMin(root);
    }

    private Node deleteMin(Node node) {

        if (node.left == null) {
            return node.right == null ? null : node.right;
        }
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    public void deleteMax() {

        if (isEmpty()) {
            throw new RuntimeException("符号表为空");
        }
        root = deleteMax(root);
    }

    private Node deleteMax(Node node) {

        if (node.right == null) {
            return node.left == null ? null : node.left;
        }
        node.right = deleteMax(node.right);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    public int size(K low, K high) {

        Objects.requireNonNull(low, "参数low不能为null");
        Objects.requireNonNull(high, "参数high不能为null");
        if (low.compareTo(high) > 0) {
            return 0;
        }
        if (contains(high)) {
            return rank(high) - rank(low) + 1;
        } else {
            return rank(high) - rank(low);
        }
    }

    public Iterable<K> keys() {
        return keys(min(), max());
    }

    public Iterable<K> keys(K low, K high) {

        List<K> list = new ArrayList<>();
        keys(root, low, high, list);
        return list;
    }

    private void keys(Node node, K low, K high, List<K> list) {

        if (node == null) {
            return;
        }
        int lowCmp = node.key.compareTo(low);
        int highCmp = node.key.compareTo(high);
        if (lowCmp > 0) {
            keys(node.left, low, high, list);
        }
        if (lowCmp >= 0 && highCmp <= 0) {
            list.add(node.key);
        }
        if (highCmp < 0) {
            keys(node.right, low, high, list);
        }
    }

    private class Node {

        private K key;
        private V value;
        private Node left;
        private Node right;
        private int size; // 这棵树的节点数目

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.size = 1;
        }
    }
}
